package leetcode_1201_1300;

import java.util.ArrayDeque;

public class LeeCode_1263 {
    public static void main(String[] args) {
        System.out.println(minPushBox(new char[][]{{'S'}, {'B'}, {'T'}, {'.'}, {'#'}}));
    }
    private static int n;
    private static int m;
    private static int minPushBox(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        int si = 0, sj = 0, bi = 0, bj = 0, ti = 0, tj = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'S'){
                    si = i;
                    sj = j;
                }
                if (grid[i][j] == 'B'){
                    bi = i;
                    bj = j;
                }
                if (grid[i][j] == 'T'){
                    ti = i;
                    tj = j;
                }
            }
        }
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        int[] dict = new int[]{-1, 0, 1, 0, -1};
        boolean[][] vis = new boolean[m * n][m * n];
        queue.addFirst(new int[]{f(si, sj), f(bi, bj), 0});
        vis[f(si, sj)][f(bi, bj)] = true;
        while (!queue.isEmpty()){
            int[] sta = queue.pollFirst();
            int d = sta[2];
            bi = sta[1] / n;
            bj = sta[1] % n;
            if (bi == ti && bj == tj) {
                return sta[2];
            }
            for (int i = 0; i < dict.length - 1; i++) {
                si = sta[0] / n ;
                sj = sta[0] % n;
                int sx = si + dict[i];
                int sy = sj + dict[i + 1];
                if (!check(sx, sy, grid)){
                    continue;
                }
                if (sx == bi && sy == bj){
                    int bx = bi + dict[i];
                    int by = bj + dict[i + 1];
                    if (!check(bx, by, grid) || vis[f(sx, sy)][f(bx, by)]){
                        continue;
                    }
                    vis[f(sx, sy)][f(bx, by)] = true;
                    queue.offer(new int[]{f(sx, sy), f(bx, by), d + 1});
                }else if (!vis[f(sx, sy)][f(bi, bj)]){
                    vis[f(sx, sy)][f(bi, bj)] = true;
                    queue.offerFirst(new int[]{f(sx, sy), f(bi, bj), d});
                }
            }
        }
        return -1;
    }
    private static int f(int i, int j){
        return i * n + j;
    }
    private static boolean check(int i, int j, char[][] grid){
       return i >= 0 && i < m && j >= 0 && j < n && grid[i][j] != '#';
    }
}
